package 力扣_滑动窗口.第三类模板;

/**
 * @author zx
 * @create 2022-05-10 21:42
 */
public class 可获得的最大点数_1423 {
    /**
     记数组cardPoints的长度为n,由于只能从开头和末尾拿k张卡牌,所以最后剩下的必然是连续的n−k张卡牌.
     求出滑动窗口最小值,然后用所有卡牌的点数之和减去该最小值,即得到了拿走卡牌点数之和的最大值.
     * @return 滑动窗口(官方思路)
     */
    public int maxScore(int[] cardPoints, int k) {
        // 滑动窗口大小为 cardPoints.length - k
        int windowSize = cardPoints.length - k;
        // 选前 cardPoints.length - k个作为初始值
        int sum = 0;
        int all = 0;//所有卡牌点数之和
        for(int i = 0;i < windowSize;i++){
            sum += cardPoints[i];
            all += cardPoints[i];
        }
        int minSum = sum;
        int left = 0;
        for(int right = windowSize;right < cardPoints.length;right++){
            all += cardPoints[right];
            // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
            sum += cardPoints[right];
            left = right - windowSize;//窗口左值是固定的：right - windowSize
            sum -= cardPoints[left];
            minSum = Math.min(minSum,sum);
        }
        return all - minSum;
    }
}
